package Offer.offer2020;

import domain.ListNode;

/**
 * 链表中的倒数第K个节点
 * 两个指针 走的速度不同， P1 先走K-1步   然后P1 和P2再同步走 这样两者永远相差K-1步
 * 等P1到达尾指针，则P2刚好达到倒数第K个节点
 * 1，2，3，4，5，6
 */
public class Test15 {

    public static void main(String[] args) {
        ListNode p1 = new ListNode(1);
        ListNode p2 = new ListNode(2);
        ListNode p3 = new ListNode(3);
        ListNode p4 = new ListNode(4);
        ListNode p5 = new ListNode(5);
        ListNode p6 = new ListNode(6);

        p1.next = p2;
        p2.next = p3;
        p3.next = p4;
        p4.next = p5;
        p5.next = p6;
        p6.next = null;

        ListNode result = findLastKNode(p1, 6);
        System.out.println(result.val);
    }

    public static ListNode findLastKNode(ListNode head, int K) {
        if (head == null) {
            throw new RuntimeException("不存在");
        }
        ListNode p1 = head;
        ListNode p2 = head;

        for (int i = 1; i <= K - 1; i++) {
            if (p1.next != null) {
                p1 = p1.next;
            } else {
                throw new RuntimeException("不存在");
            }
        }

        while (p1.next != null) {
            p1 = p1.next;
            p2 = p2.next;
        }

        return p2;
    }
}
